package leetcode.editor.cn;

//Java：链表相交
public class IntersectionOfTwoLinkedListsLcci {
    public static void main(String[] args) {
        Solution solution = new IntersectionOfTwoLinkedListsLcci().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
    /**
     * 思路：两个链表相交处，后面的元素都是相同的，所以检查的切入点应该是最短链表的起始处，同时后移找相同节点
     * 注意点：算完A和B的长度后，记得将curA和curB还原到初始位置
     */
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode curA = headA;
            ListNode curB = headB;
            int lengA = 0;
            int lengB = 0;
            while (curA != null) {
                curA = curA.next;
                lengA++;
            }
            while (curB != null) {
                curB = curB.next;
                lengB++;
            }

            //还原到初始位置
            curA = headA;
            curB = headB;

            //如果B更长，交换一下
            if (lengB > lengA) {
                int temp = lengA;
                lengA = lengB;
                lengB = temp;

                ListNode tempNode = curA;
                curA = curB;
                curB = tempNode;
            }

            int grep = lengA - lengB;
            while (grep-- > 0) {
                curA = curA.next;
            }
            while (curA != null) {
                if (curA == curB) {
                    return curA;
                }
                curA = curA.next;
                curB = curB.next;
            }
            return null;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}